#include<string.h>
#include<assert.h>
#include<iostream>

using namespace std;

int NaiveStrMatching(const string & T, const string & P){
    int p = 0;
    int t = 0;
    int plen = P.length();
    int tlen = T.length();
    if(tlen < plen)
        return -1;
    while(p < plen && t < tlen){
        if(T[t] == P[p]){
            p++;
            t++;
        }
        else
        {
            t = t - p + 1;
            p = 0;
        }
    }
        if(p >= plen)
            return (t - plen + 1);
        else
            return -1;
}

int Strcmp(char * s1, char * s2){
    int counter = 0;
    while(s1[counter] != '\0' && s2[counter] != '\0'){
        if(s1[counter] > s2[counter])
            return 1;
        else if(s1[counter] < s2[counter])
            return -1;
        counter++;
    }
    if(s1[counter] == '\0' && s2[counter] != '\0')
        return -1;
    else if(s1[counter] != '\0' && s2[counter] == '\0')
        return -1;
    return 0;
}

int findLast(const string & T, const string & P){
    int p = 0;
    int t = 0;
    int plen = P.length();
    int tlen = T.length();
    while(1){
        if(tlen < plen)
            return -1;
        if(tlen - t < plen)
            return (t - 1);
        while(p < plen && t < tlen){
            if(T[t] == P[p]){
                p++;
                t++;
            }
            else
            {
                t = t - p + 1;
                p = 0;
            }
        }
        if(p >= plen){
            p = 0;
            t = t - plen + 2;
        }
    }
}

int main(){
    string s1 = "helloworld";
    string s2 = "ello";
    string s3 = "elloa";
    cout<<NaiveStrMatching(s1, s2)<<' '<<NaiveStrMatching(s1, s3)<<endl;
    char s4[] = "abc";
    char s5[] = "abd";
    char s6[] = "abb";
    char s7[] = "abc";
    cout<<Strcmp(s4, s5)<<' '<<Strcmp(s4, s6)<<' '<<Strcmp(s4, s7)<<endl;
    string s8 = "colacoco";
    string s9 = "co";
    cout<<findLast(s8, s9)<<endl;

    return 0;
}
